package com.sun;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/3sum-closest/
 * 给你一个长度为 n 的整数数组nums和 一个目标值target。请你从 nums 中选出三个整数，使它们的和与target最接近。
 * 返回这三个数的和。
 * 假定每组输入只存在恰好一个解。
 */
public class Test16最接近的三数之和 {
    public static void main(String[] args) {
        int[] nums = {-1000,-5,-5,-5,-5,-5,-5,-1,-1,-1};
        int res = threeSumClosest2(nums, -14);
        System.out.println(res);
    }

    /**
     *方法1：自己三层暴力循环
     */
    public static int threeSumClosest1(int[] nums, int target) {
        int res = nums[0] + nums[1] + nums[2];
        int n = nums.length;
        Arrays.sort(nums);
        for (int first = 0; first < n; first++){
            if (first > 0 && nums[first] == nums[first -1]){
                continue;
            }
            for (int second = first + 1; second < n; second++){
                if (second > first + 1 && nums[second] == nums[second - 1]){
                    continue;
                }
                for (int third = second + 1;third < n ;third++){
                    int sum = nums[first] + nums[second] + nums[third];
                    if(Math.abs(target - sum) < Math.abs(target - res)){
                        res = sum;
                    }
                }
            }
        }
        return res;
    }

    /**
     *方法2：力扣思路
     */
    public static int threeSumClosest2(int[] nums, int target) {
        int n = nums.length;
        Arrays.sort(nums);
        int res = nums[0] + nums[1] + nums[2];
        for(int first = 0; first < n; first++){
            if (first > 0 && nums[first] == nums[first -1]){
                continue;
            }
            int third = n - 1;
            for (int second = first + 1; second < n;){
                if (second == third){
                    break;
                }
                System.out.print(nums[first]+" ");
                System.out.print(nums[second]+" ");
                System.out.println(nums[third]);
                int sum = nums[first] + nums[second] + nums[third];
                res = Math.abs(target - sum) < Math.abs(target - res) ? sum : res;
                if (sum == target){
                    return res;
                } else if (second < third && sum > target){
                    third--;
                    while (third > second && nums[third] == nums[third+1]){
                        third--;
                    }

                }if (second < third && sum < target){
                    second ++;
                    while (second < third && nums[second] == nums[second-1]){
                        second++;
                    }
                }
            }
        }
        return res;
    }
}
